package LinkList;

public class MySingleList implements IList{
    static class ListNode{
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public void CreateList(){
        ListNode node1=new ListNode(1);
        ListNode node2=new ListNode(2);
        ListNode node3=new ListNode(3);
        ListNode node4=new ListNode(4);
        ListNode node5=new ListNode(5);

        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        this.head=node1;

    }

    public ListNode head;

    //头插法
    public void addFirst(int data){
        ListNode firstnode=new ListNode(data);
        firstnode.next=head;
        head=firstnode;
    }
    //尾插法
    public void addLast(int data){
        ListNode lastnode=new ListNode(data);
        while(head==null){
            head=lastnode;
            return;
        }
        ListNode cur=head;
        while(cur.next!=null){
            cur=cur.next;
        }
        cur.next=lastnode;
        return;

    }

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        int len=size();
        if(0<index||index>len){
            System.out.println("插入位置不合法");
        }
        if(index==0){
            addFirst(data);
        }
        if(index==len){
            addLast(data);
        }
        //中间插入
        ListNode cur=head;
        while(index-1!=0){
            cur=cur.next;
            index--;
        }
        ListNode node=new ListNode(data);
        node.next=cur.next;
        cur.next=node;
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        ListNode cur=head;
        while(cur!=null){
            if(cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }

    //删除第一次出现关键字为key的节点
    public void remove(int key){
        if(head==null){
            return;
        }
        if(head.val==key){
            head=head.next;
            return;
        }
        ListNode cur=findNodeOfkey(key);
        if(cur==null){
            return;
        }
        ListNode del=cur.next;
        cur.next=del.next;
    }

    public ListNode findNodeOfkey(int key){
        ListNode cur=head;
        while(cur.next!=null){
            if(cur.next.val==key){
                return cur;
            }
            cur=cur.next;
        }
        return null;
    }

    //删除所有值为key的节点

    //得到单链表的长度
    public int size(){
        int len=0;
        ListNode node=head;
        while(node!=null){
            len++;
            node=node.next;
        }
        return len;
    }

    public void removeAllKey(int key) {
        if(head == null) {
            return;
        }
        ListNode prev = head;
        ListNode cur = head.next;
        while (cur != null) {
            if(cur.val == key) {//prev始终都没改变
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;//prev现在相当于指向prev的下一个节点
                cur = cur.next;
            }
        }
        if(head.val == key) {
            head = head.next;
        }
    }


    public void clear(){
        ListNode cur=head;
        while (cur!=null){
            ListNode curN=cur.next;
            cur.next=null;
            cur=curN;
        }
        head=null;//第二种方法，最暴力，
    }
    public void display(){
        ListNode cur=head;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        };
        System.out.println();
    }

    //反转链表
    public ListNode reverseList(){
        if(head==null){
            return head;
        }
        ListNode cur=head.next;
        head.next=null;
        while (cur!=null){
            ListNode curN=cur.next;
            cur.next=head;
            head=cur;
            cur=curN;
        }
        return head;
    }

    //不求长度查找中间结点

    public ListNode middleNode() {
        if (head == null) {
            return null;
        }
        ListNode slow=head;
        ListNode fast=head;

        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }

    //获取链表倒数第k个节点
    public ListNode getK(int k){
        if(head==null){
            return null;
        }
        ListNode first=head;
        ListNode two=head;
        int count=0;
        while(count+1!=k){
            two=two.next;
            count++;
        }
        while (two.next!=null){
            first=first.next;
            two=two.next;
        }
        return first;
    }


    public ListNode partition(int x){
        if(head==null){
            return null;
        }
        ListNode ss=null;
        ListNode se=null;
        ListNode bs=null;
        ListNode be=null;

        ListNode cur=head;
        while(cur!=null){
            if(cur.val<x){
                //第一次插入
                if(ss==null){
                    ss=se=cur;
                }else{
                    se.next=cur;
                    se=se.next;
                }
            }else {
                if(bs==null){
                    bs=be=cur;
                }else {
                    be.next=cur;
                    be=be.next;
                }
            }
            cur=cur.next;
        }
        if(ss==null){
            return bs;
        }
        if(bs==null){
            return ss;
        }
        se.next=bs;
        if(bs!=null){
            be.next=null;
        }
        return ss;
    }

    //回文
    public boolean chkPalindrome() {
        // write code here
        if(head==null){
            return false;
        }
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null||fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //逆置后面链表
        ListNode cur=slow.next;
        while(cur!=null){
            ListNode curN=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curN;
        }
        //3判断回文
        while(head!=slow){
            if(head.val!=slow.val){
                return false;
            }
            if(head.next==slow){
                return true;
            }
            head=head.next;
            slow=slow.next;
        }
        return true;
    }
    //找公共节点
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int sizeA = 0;
        int sizeB = 0;
        ListNode endA = null;
        ListNode endB = null;
        ListNode curA = headA;
        ListNode curB = headB;
        //遍历listA获取endA,sizeA
        while(curA != null){
            sizeA++;
            if(curA.next == null){
                endA = curA;
            }
            curA = curA.next;
        }
        //遍历listB获取endB,sizeB
        while(curB != null){
            sizeB++;
            if(curB.next == null){
                endB = curB;
            }
            curB = curB.next;
        }
        //判断是否相交
        if(endA != endB){
            return null;
        }
        //再走一遍listA,listB，长链表先走
        curA = headA;
        curB = headB;
        if(sizeA > sizeB){
            while (sizeA > sizeB){
                curA = curA.next;
                sizeA--;
            }
        }else{
            while(sizeA < sizeB){
                curB = curB.next;
                sizeB--;
            }
        }
        //长链表已走完差值节点，两个链表指针一起走，找第一个相交的节点
        while(curA!=null && curB!=null){
            if(curA == curB){
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }
}
